<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 4.2.1">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/32x32.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/16x16.png">

<link rel="stylesheet" href="/css/main.css">

<link rel="stylesheet" href="//fonts.googleapis.com/css?family=Lato:300,300italic,400,400italic,700,700italic|Lato', 'Microsoft Yahei Light:300,300italic,400,400italic,700,700italic|Cambria', 'Microsoft Yahei Light:300,300italic,400,400italic,700,700italic|Verdana', Lato, 'Microsoft Yahei Light:300,300italic,400,400italic,700,700italic&display=swap&subset=latin,latin-ext">
<link rel="stylesheet" href="/lib/font-awesome/css/all.min.css">

<script id="hexo-configurations">
    var NexT = window.NexT || {};
    var CONFIG = {"hostname":"yoursite.com","root":"/","scheme":"Mist","version":"7.8.0","exturl":false,"sidebar":{"position":"right","display":"hide","padding":18,"offset":12,"onmobile":false},"copycode":{"enable":false,"show_result":false,"style":null},"back2top":{"enable":true,"sidebar":false,"scrollpercent":false},"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"algolia":{"hits":{"per_page":10},"labels":{"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}},"localsearch":{"enable":true,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},"path":"search.xml"};
  </script>

  <meta name="description" content="Problem 644 Squares on the lineSam and Tom are trying a game of (partially) covering a given line segment of length $L$ by taking turns in placing unit squares onto the line segment. As illustrated b">
<meta property="og:type" content="article">
<meta property="og:title" content="Problem 644">
<meta property="og:url" content="http://yoursite.com/644/index.html">
<meta property="og:site_name" content="Project Euler | 欧拉计划">
<meta property="og:description" content="Problem 644 Squares on the lineSam and Tom are trying a game of (partially) covering a given line segment of length $L$ by taking turns in placing unit squares onto the line segment. As illustrated b">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://projecteuler.net/project/images/p644_squareline.png">
<meta property="og:image" content="https://projecteuler.net/project/images/p644_squareline.png">
<meta property="article:published_time" content="2018-11-25T06:00:00.000Z">
<meta property="article:modified_time" content="2020-09-13T02:36:56.287Z">
<meta property="article:author" content="sx349">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://projecteuler.net/project/images/p644_squareline.png">

<link rel="canonical" href="http://yoursite.com/644/">


<script id="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome : false,
    isPost : true,
    lang   : 'zh-CN'
  };
</script>

  <title>Problem 644 | Project Euler | 欧拉计划</title>
  






  <noscript>
  <style>
  .use-motion .brand,
  .use-motion .menu-item,
  .sidebar-inner,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line-before i { left: initial; }
  .use-motion .logo-line-after i { right: initial; }
  </style>
</noscript>

</head>

<body itemscope itemtype="http://schema.org/WebPage">
  <div class="container use-motion">
    <div class="headband"></div>

    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏">
      <span class="toggle-line toggle-line-first"></span>
      <span class="toggle-line toggle-line-middle"></span>
      <span class="toggle-line toggle-line-last"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/" class="brand" rel="start">
      <span class="logo-line-before"><i></i></span>
      <h1 class="site-title">Project Euler | 欧拉计划</h1>
      <span class="logo-line-after"><i></i></span>
    </a>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>




<nav class="site-nav">
  <ul id="menu" class="main-menu menu">
        <li class="menu-item menu-item-home">

    <a href="/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a>

  </li>
        <li class="menu-item menu-item-problem">

    <a href="/problems" rel="section"><i class="fa fa-tags fa-fw"></i>题目</a>

  </li>
        <li class="menu-item menu-item-about">

    <a href="/about/" rel="section"><i class="fa fa-user fa-fw"></i>关于</a>

  </li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
        </a>
      </li>
  </ul>
</nav>



  <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
  <span class="search-icon">
    <i class="fa fa-search"></i>
  </span>
  <div class="search-input-container">
    <input autocomplete="off" autocapitalize="off"
           placeholder="搜索..." spellcheck="false"
           type="search" class="search-input">
  </div>
  <span class="popup-btn-close">
    <i class="fa fa-times-circle"></i>
  </span>
</div>
<div id="search-result">
  <div id="no-result">
    <i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>
  </div>
</div>

    </div>
  </div>

</div>
    </header>

    
  <div class="back-to-top">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>


    <main class="main">
      <div class="main-inner">
        <div class="content-wrap">
          

          <div class="content post posts-expand">
            

    
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/644/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.png">
      <meta itemprop="name" content="sx349">
      <meta itemprop="description" content="Project Euler | 欧拉计划 中文翻译站">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Project Euler | 欧拉计划">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          Problem 644
        </h1>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-calendar"></i>
              </span>
              <span class="post-meta-item-text">题目发布于</span>

              <time title="发布时间：2018-11-24 22:00:00" itemprop="dateCreated datePublished" datetime="2018-11-24T22:00:00-08:00">2018-11-24</time>
            </span>
              <span class="post-meta-item">
                <span class="post-meta-item-icon">
                  <i class="far fa-calendar-check"></i>
                </span>
                <span class="post-meta-item-text">翻译更新于</span>
                <time title="更新时间：2020-09-12 19:36:56" itemprop="dateModified" datetime="2020-09-12T19:36:56-07:00">2020-09-12</time>
              </span>

          

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
        <hr>
<h1 id="Problem-644"><a href="#Problem-644" class="headerlink" title="Problem 644"></a><a href="https://projecteuler.net/problem=644" target="_blank" rel="noopener">Problem 644</a></h1><hr>
<h2 id="Squares-on-the-line"><a href="#Squares-on-the-line" class="headerlink" title="Squares on the line"></a><strong>Squares on the line</strong></h2><p>Sam and Tom are trying a game of (partially) covering a given line segment of length $L$ by taking turns in placing unit squares onto the line segment.</p>
<p>As illustrated below, the squares may be positioned in two different ways, either “straight” by placing the midpoints of two opposite sides on the line segment, or “diagonal” by placing two opposite corners on the line segment. Newly placed squares may touch other squares, but are not allowed to overlap any other square laid down before.<br>The player who is able to place the last unit square onto the line segment wins.</p>
<p><img src="https://projecteuler.net/project/images/p644_squareline.png" alt="p644_squareline.png"></p>
<p>With Sam starting each game by placing the first square, they quickly realise that Sam can easily win every time by placing the first square in the middle of the line segment, making the game boring.</p>
<p>Therefore they decide to randomise Sam’s first move, by first tossing a fair coin to determine whether the square will be placed straight or diagonal onto the line segment and then choosing the actual position on the line segment randomly with all possible positions being equally likely. Sam’s gain of the game is defined to be $0$ if he loses the game and $L$ if he wins. Assuming optimal play of both players after Sam’s initial move, you can see that Sam’s expected gain, called $e(L)$, is only dependent on the length of the line segment.</p>
<p>For example, if $L=2$, Sam will win with a probability of $1$, so $e(2)=2$.<br>Choosing $L=4$, the winning probability will be $0.33333333$ for the straight case and $0.22654092$ for the diagonal case, leading to $e(4)=1.11974851$ (rounded to $8$ digits after the decimal point each).</p>
<p>Being interested in the optimal value of $L$ for Sam, let’s define $f(a,b)$ to be the maximum of $e(L)$ for some $L\in[a,b]$.<br>You are given $f(2,10)=2.61969775$, being reached for $L=7.82842712$, and $f(10,20)=5.99374121$ (rounded to $8$ digits each).</p>
<p>Find $f(200,500)$, rounded to $8$ digits after the decimal point.</p>
<hr>
<h2 id="线段的正方形覆盖"><a href="#线段的正方形覆盖" class="headerlink" title="线段的正方形覆盖"></a><strong>线段的正方形覆盖</strong></h2><p>山姆和汤姆正在玩一个游戏：在一条长为$L$的线段上，他们轮流摆放单位正方形，以（部分地）覆盖这个线段。</p>
<p>如下图所示，有两种摆放正方形的方式，一种是“横放”，将正方形两条对边的中点放在线段上，另一种是“斜放”，将正方形沿对角线放在线段上。后放的正方形可以与先放的正方形接触，但是不允许重叠。<br>如果在一名玩家摆放完正方形之后，对方无法再摆放新的正方形，则前者获胜。</p>
<p><img src="https://projecteuler.net/project/images/p644_squareline.png" alt="p644_squareline.png"></p>
<p>一开始，总是由山姆先摆放正方形，但他们很快发现，山姆只需把第一个正方形摆放在线段正中间，就必定能够获胜，这样的游戏太无聊了。</p>
<p>于是他们决定，山姆必须随机摆放第一个正方形：先抛掷一枚公平硬币，决定这个正方形是横放还是斜放，然后再在线段上等概率地选择正方形摆放的位置。双方约定，如果山姆输了，那么他的收益为$0$，反之他的收益为$L$。在摆完第一个正方形之后，如果双方都采用最优策略，可以看出山姆的期望收益$e(L)$只取决于线段的长度。</p>
<p>例如，如果$L=2$，山姆必定获胜，所以$e(2)=2$。<br>如果$L=4$，当第一个正方形横放时，山姆获胜的概率是$0.33333333$，而斜放时概率是$0.22654092$，因此$e(4)=1.11974851$（均保留小数点后$8$位小数）。</p>
<p>我们希望知道，在一定范围内，对山姆来说最优的线段长度$L$应该是多少，因此我们记$f(a,b)$为所有$L\in[a,b]$对应的$e(L)$中的最大值。<br>已知$f(2,10)=2.61969775$，此时最优长度为$L=7.82842712$；我们还知道$f(10,20)=5.99374121$（均保留小数点后$8$位小数）。</p>
<p>求$f(200,500)$，并保留小数点后$8$位小数。</p>
<hr>

    </div>

    
    
    

      <footer class="post-footer">

        


        
    <div class="post-nav">
      <div class="post-nav-item">
    <a href="/643/" rel="prev" title="Problem 643">
      <i class="fa fa-chevron-left"></i> Problem 643
    </a></div>
      <div class="post-nav-item">
    <a href="/645/" rel="next" title="Problem 645">
      Problem 645 <i class="fa fa-chevron-right"></i>
    </a></div>
    </div>
      </footer>
    
  </article>
  
  
  



          </div>
          
    <div class="comments" id="gitalk-container"></div>

<script>
  window.addEventListener('tabs:register', () => {
    let { activeClass } = CONFIG.comments;
    if (CONFIG.comments.storage) {
      activeClass = localStorage.getItem('comments_active') || activeClass;
    }
    if (activeClass) {
      let activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
      if (activeTab) {
        activeTab.click();
      }
    }
  });
  if (CONFIG.comments.storage) {
    window.addEventListener('tabs:click', event => {
      if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
      let commentClass = event.target.classList[1];
      localStorage.setItem('comments_active', commentClass);
    });
  }
</script>

        </div>
          
  
  <div class="toggle sidebar-toggle">
    <span class="toggle-line toggle-line-first"></span>
    <span class="toggle-line toggle-line-middle"></span>
    <span class="toggle-line toggle-line-last"></span>
  </div>

  <aside class="sidebar">
    <div class="sidebar-inner">

      <ul class="sidebar-nav motion-element">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <!--noindex-->
      <div class="post-toc-wrap sidebar-panel">
          <div class="post-toc motion-element"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#Problem-644"><span class="nav-text">Problem 644</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#Squares-on-the-line"><span class="nav-text">Squares on the line</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#线段的正方形覆盖"><span class="nav-text">线段的正方形覆盖</span></a></li></ol></li></ol></div>
      </div>
      <!--/noindex-->

      <div class="site-overview-wrap sidebar-panel">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image" alt="sx349"
      src="/images/avatar.png">
  <p class="site-author-name" itemprop="name">Leonhard Euler(1707-1783)</p>
  <p class="site-description motion-element">Project Euler | 欧拉计划<br>中文翻译站</p>
</div>
  <div class="cc-license motion-element" itemprop="license">
    <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" class="cc-opacity" rel="noopener" target="_blank"><img src="/images/cc-by-nc-sa.svg" alt="Creative Commons"></a>
  </div>


  <div class="links-of-blogroll motion-element">
    <div class="links-of-blogroll-title"><i class="fa fa-link fa-fw"></i>
      友情链接
    </div>
    <ul class="links-of-blogroll-list">
        <li class="links-of-blogroll-title">
          <a href="https://projecteuler.net/" title="https:&#x2F;&#x2F;projecteuler.net" rel="noopener" target="_blank">Project Euler</a>
        </li>
        <li class="links-of-blogroll-title">
          <a href="http://jakwings.is-programmer.com/Project_Euler" title="http:&#x2F;&#x2F;jakwings.is-programmer.com&#x2F;Project_Euler" rel="noopener" target="_blank">饮水思源汉化</a>
        </li>
        <li class="links-of-blogroll-title">
          <a href="http://sx349.github.io/" title="http:&#x2F;&#x2F;sx349.github.io" rel="noopener" target="_blank">译者博客</a>
        </li>
    </ul>
  </div>

      </div>

    </div>
  </aside>
  <div id="sidebar-dimmer"></div>


      </div>
    </main>

    <footer class="footer">
      <div class="footer-inner">
        

        

<div class="copyright">
  
  &copy; 2001 – 
  <span itemprop="copyrightYear">2021</span>
  <span class="with-love">
    <i class="fas fa-calculator"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">Project Euler | 欧拉计划</span>
</div>
  <div class="powered-by">由 <a href="https://hexo.io/" class="theme-link" rel="noopener" target="_blank">Hexo</a> & <a href="https://mist.theme-next.org/" class="theme-link" rel="noopener" target="_blank">NexT.Mist</a> 强力驱动
  </div>

        








      </div>
    </footer>
  </div>

  
  <script src="/lib/anime.min.js"></script>
  <script src="/lib/velocity/velocity.min.js"></script>
  <script src="/lib/velocity/velocity.ui.min.js"></script>

<script src="/js/utils.js"></script>

<script src="/js/motion.js"></script>


<script src="/js/schemes/muse.js"></script>


<script src="/js/next-boot.js"></script>




  




  
<script src="/js/local-search.js"></script>













  

  
      

<script>
  if (typeof MathJax === 'undefined') {
    window.MathJax = {
      loader: {
        source: {
          '[tex]/amsCd': '[tex]/amscd',
          '[tex]/AMScd': '[tex]/amscd'
        }
      },
      tex: {
        inlineMath: {'[+]': [['$', '$']]},
        tags: 'ams'
      },
      options: {
        renderActions: {
          findScript: [10, doc => {
            document.querySelectorAll('script[type^="math/tex"]').forEach(node => {
              const display = !!node.type.match(/; *mode=display/);
              const math = new doc.options.MathItem(node.textContent, doc.inputJax[0], display);
              const text = document.createTextNode('');
              node.parentNode.replaceChild(text, node);
              math.start = {node: text, delim: '', n: 0};
              math.end = {node: text, delim: '', n: 0};
              doc.math.push(math);
            });
          }, '', false],
          insertedScript: [200, () => {
            document.querySelectorAll('mjx-container').forEach(node => {
              let target = node.parentNode;
              if (target.nodeName.toLowerCase() === 'li') {
                target.parentNode.classList.add('has-jax');
              }
            });
          }, '', false]
        }
      }
    };
    (function () {
      var script = document.createElement('script');
      script.src = '//cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js';
      script.defer = true;
      document.head.appendChild(script);
    })();
  } else {
    MathJax.startup.document.state(0);
    MathJax.texReset();
    MathJax.typeset();
  }
</script>

    

  

<link rel="stylesheet" href="//cdn.jsdelivr.net/npm/gitalk@1/dist/gitalk.min.css">

<script>
NexT.utils.loadComments(document.querySelector('#gitalk-container'), () => {
  NexT.utils.getScript('//cdn.jsdelivr.net/npm/gitalk@1/dist/gitalk.min.js', () => {
    var gitalk = new Gitalk({
	  title       : document.title.substr(0,29),
      clientID    : '4ba99a8839c5e7dde683',
      clientSecret: '3984f7cad409553d6afde8dbc2c08fc425e7bbdc',
      repo        : 'pe-cn-comments',
      owner       : 'pe-cn',
      admin       : ['sx349'],
      id          : '5dbefdb48fb8846f1c1d1ab0dbd34ab8',
        language: '',
      distractionFreeMode: true
    });
    gitalk.render('gitalk-container');
  }, window.Gitalk);
});
</script>

</body>
</html>
